home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2009 February / PCWFEB09.iso / Software / Resources / Chat & Communication / Digsby build 37 / digsby_setup.exe / lib / difflib.pyo (.txt) < prev    next >
Encoding:
Python Compiled Bytecode  |  2008-10-13  |  25.6 KB  |  942 lines
  1. # Source Generated with Decompyle++
  2. # File: in.pyo (Python 2.5)
  3.  
  4. __all__ = [
  5.     'get_close_matches',
  6.     'ndiff',
  7.     'restore',
  8.     'SequenceMatcher',
  9.     'Differ',
  10.     'IS_CHARACTER_JUNK',
  11.     'IS_LINE_JUNK',
  12.     'context_diff',
  13.     'unified_diff',
  14.     'HtmlDiff']
  15. import heapq
  16.  
  17. def _calculate_ratio(matches, length):
  18.     if length:
  19.         return 2 * matches / length
  20.     
  21.     return 1
  22.  
  23.  
  24. class SequenceMatcher:
  25.     
  26.     def __init__(self, isjunk = None, a = '', b = ''):
  27.         self.isjunk = isjunk
  28.         self.a = None
  29.         self.b = None
  30.         self.set_seqs(a, b)
  31.  
  32.     
  33.     def set_seqs(self, a, b):
  34.         self.set_seq1(a)
  35.         self.set_seq2(b)
  36.  
  37.     
  38.     def set_seq1(self, a):
  39.         if a is self.a:
  40.             return None
  41.         
  42.         self.a = a
  43.         self.matching_blocks = None
  44.         self.opcodes = None
  45.  
  46.     
  47.     def set_seq2(self, b):
  48.         if b is self.b:
  49.             return None
  50.         
  51.         self.b = b
  52.         self.matching_blocks = None
  53.         self.opcodes = None
  54.         self.fullbcount = None
  55.         self._SequenceMatcher__chain_b()
  56.  
  57.     
  58.     def __chain_b(self):
  59.         b = self.b
  60.         n = len(b)
  61.         self.b2j = b2j = { }
  62.         populardict = { }
  63.         for i, elt in enumerate(b):
  64.             if elt in b2j:
  65.                 indices = b2j[elt]
  66.                 if n >= 200 and len(indices) * 100 > n:
  67.                     populardict[elt] = 1
  68.                     del indices[:]
  69.                 else:
  70.                     indices.append(i)
  71.             len(indices) * 100 > n
  72.             b2j[elt] = [
  73.                 i]
  74.         
  75.         for elt in populardict:
  76.             del b2j[elt]
  77.         
  78.         isjunk = self.isjunk
  79.         junkdict = { }
  80.         if isjunk:
  81.             for d in (populardict, b2j):
  82.                 for elt in d.keys():
  83.                     if isjunk(elt):
  84.                         junkdict[elt] = 1
  85.                         del d[elt]
  86.                         continue
  87.                 
  88.             
  89.         
  90.         self.isbjunk = junkdict.has_key
  91.         self.isbpopular = populardict.has_key
  92.  
  93.     
  94.     def find_longest_match(self, alo, ahi, blo, bhi):
  95.         (a, b, b2j, isbjunk) = (self.a, self.b, self.b2j, self.isbjunk)
  96.         besti = alo
  97.         bestj = blo
  98.         bestsize = 0
  99.         j2len = { }
  100.         nothing = []
  101.         for i in xrange(alo, ahi):
  102.             j2lenget = j2len.get
  103.             newj2len = { }
  104.             for j in b2j.get(a[i], nothing):
  105.                 if j < blo:
  106.                     continue
  107.                 
  108.                 if j >= bhi:
  109.                     break
  110.                 
  111.                 k = newj2len[j] = j2lenget(j - 1, 0) + 1
  112.                 if k > bestsize:
  113.                     besti = (i - k) + 1
  114.                     bestj = (j - k) + 1
  115.                     bestsize = k
  116.                     continue
  117.             
  118.             j2len = newj2len
  119.         
  120.         while besti > alo and bestj > blo and not isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  121.             besti = besti - 1
  122.             bestj = bestj - 1
  123.             bestsize = bestsize + 1
  124.         while besti + bestsize < ahi and bestj + bestsize < bhi and not isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  125.             bestsize += 1
  126.         while besti > alo and bestj > blo and isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  127.             besti = besti - 1
  128.             bestj = bestj - 1
  129.             bestsize = bestsize + 1
  130.         while besti + bestsize < ahi and bestj + bestsize < bhi and isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  131.             bestsize = bestsize + 1
  132.         return (besti, bestj, bestsize)
  133.  
  134.     
  135.     def get_matching_blocks(self):
  136.         if self.matching_blocks is not None:
  137.             return self.matching_blocks
  138.         
  139.         la = len(self.a)
  140.         lb = len(self.b)
  141.         queue = [
  142.             (0, la, 0, lb)]
  143.         matching_blocks = []
  144.         while queue:
  145.             (alo, ahi, blo, bhi) = queue.pop()
  146.             (i, j, k) = x = self.find_longest_match(alo, ahi, blo, bhi)
  147.             if k:
  148.                 matching_blocks.append(x)
  149.                 if alo < i and blo < j:
  150.                     queue.append((alo, i, blo, j))
  151.                 
  152.                 if i + k < ahi and j + k < bhi:
  153.                     queue.append((i + k, ahi, j + k, bhi))
  154.                 
  155.             j + k < bhi
  156.         matching_blocks.sort()
  157.         i1 = j1 = k1 = 0
  158.         non_adjacent = []
  159.         for i2, j2, k2 in matching_blocks:
  160.             if i1 + k1 == i2 and j1 + k1 == j2:
  161.                 k1 += k2
  162.                 continue
  163.             if k1:
  164.                 non_adjacent.append((i1, j1, k1))
  165.             
  166.             i1 = i2
  167.             j1 = j2
  168.             k1 = k2
  169.         
  170.         if k1:
  171.             non_adjacent.append((i1, j1, k1))
  172.         
  173.         non_adjacent.append((la, lb, 0))
  174.         self.matching_blocks = non_adjacent
  175.         return self.matching_blocks
  176.  
  177.     
  178.     def get_opcodes(self):
  179.         if self.opcodes is not None:
  180.             return self.opcodes
  181.         
  182.         i = j = 0
  183.         self.opcodes = answer = []
  184.         for ai, bj, size in self.get_matching_blocks():
  185.             tag = ''
  186.             if i < ai and j < bj:
  187.                 tag = 'replace'
  188.             elif i < ai:
  189.                 tag = 'delete'
  190.             elif j < bj:
  191.                 tag = 'insert'
  192.             
  193.             if tag:
  194.                 answer.append((tag, i, ai, j, bj))
  195.             
  196.             i = ai + size
  197.             j = bj + size
  198.             if size:
  199.                 answer.append(('equal', ai, i, bj, j))
  200.                 continue
  201.         
  202.         return answer
  203.  
  204.     
  205.     def get_grouped_opcodes(self, n = 3):
  206.         codes = self.get_opcodes()
  207.         if not codes:
  208.             codes = [
  209.                 ('equal', 0, 1, 0, 1)]
  210.         
  211.         if codes[0][0] == 'equal':
  212.             (tag, i1, i2, j1, j2) = codes[0]
  213.             codes[0] = (tag, max(i1, i2 - n), i2, max(j1, j2 - n), j2)
  214.         
  215.         if codes[-1][0] == 'equal':
  216.             (tag, i1, i2, j1, j2) = codes[-1]
  217.             codes[-1] = (tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n))
  218.         
  219.         nn = n + n
  220.         group = []
  221.         for tag, i1, i2, j1, j2 in codes:
  222.             if tag == 'equal' and i2 - i1 > nn:
  223.                 group.append((tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n)))
  224.                 yield group
  225.                 group = []
  226.                 i1 = max(i1, i2 - n)
  227.                 j1 = max(j1, j2 - n)
  228.             
  229.             group.append((tag, i1, i2, j1, j2))
  230.         
  231.         if group:
  232.             if len(group) == 1:
  233.                 pass
  234.             if not (group[0][0] == 'equal'):
  235.                 yield group
  236.             
  237.  
  238.     
  239.     def ratio(self):
  240.         matches = reduce((lambda sum, triple: sum + triple[-1]), self.get_matching_blocks(), 0)
  241.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  242.  
  243.     
  244.     def quick_ratio(self):
  245.         if self.fullbcount is None:
  246.             self.fullbcount = fullbcount = { }
  247.             for elt in self.b:
  248.                 fullbcount[elt] = fullbcount.get(elt, 0) + 1
  249.             
  250.         
  251.         fullbcount = self.fullbcount
  252.         avail = { }
  253.         availhas = avail.has_key
  254.         matches = 0
  255.         for elt in self.a:
  256.             if availhas(elt):
  257.                 numb = avail[elt]
  258.             else:
  259.                 numb = fullbcount.get(elt, 0)
  260.             avail[elt] = numb - 1
  261.             if numb > 0:
  262.                 matches = matches + 1
  263.                 continue
  264.         
  265.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  266.  
  267.     
  268.     def real_quick_ratio(self):
  269.         la = len(self.a)
  270.         lb = len(self.b)
  271.         return _calculate_ratio(min(la, lb), la + lb)
  272.  
  273.  
  274.  
  275. def get_close_matches(word, possibilities, n = 3, cutoff = 0.6):
  276.     if not n > 0:
  277.         raise ValueError('n must be > 0: %r' % (n,))
  278.     
  279.     if cutoff <= cutoff:
  280.         pass
  281.     elif not cutoff <= 1:
  282.         raise ValueError('cutoff must be in [0.0, 1.0]: %r' % (cutoff,))
  283.     
  284.     result = []
  285.     s = SequenceMatcher()
  286.     s.set_seq2(word)
  287.     for x in possibilities:
  288.         s.set_seq1(x)
  289.         if s.real_quick_ratio() >= cutoff and s.quick_ratio() >= cutoff and s.ratio() >= cutoff:
  290.             result.append((s.ratio(), x))
  291.             continue
  292.         0
  293.     
  294.     result = heapq.nlargest(n, result)
  295.     return [ x for score, x in result ]
  296.  
  297.  
  298. def _count_leading(line, ch):
  299.     i = 0
  300.     n = len(line)
  301.     while i < n and line[i] == ch:
  302.         i += 1
  303.     return i
  304.  
  305.  
  306. class Differ:
  307.     
  308.     def __init__(self, linejunk = None, charjunk = None):
  309.         self.linejunk = linejunk
  310.         self.charjunk = charjunk
  311.  
  312.     
  313.     def compare(self, a, b):
  314.         cruncher = SequenceMatcher(self.linejunk, a, b)
  315.         for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():
  316.             if tag == 'replace':
  317.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  318.             elif tag == 'delete':
  319.                 g = self._dump('-', a, alo, ahi)
  320.             elif tag == 'insert':
  321.                 g = self._dump('+', b, blo, bhi)
  322.             elif tag == 'equal':
  323.                 g = self._dump(' ', a, alo, ahi)
  324.             else:
  325.                 raise ValueError, 'unknown tag %r' % (tag,)
  326.             for line in g:
  327.                 yield line
  328.             
  329.         
  330.  
  331.     
  332.     def _dump(self, tag, x, lo, hi):
  333.         for i in xrange(lo, hi):
  334.             yield '%s %s' % (tag, x[i])
  335.         
  336.  
  337.     
  338.     def _plain_replace(self, a, alo, ahi, b, blo, bhi):
  339.         if bhi - blo < ahi - alo:
  340.             first = self._dump('+', b, blo, bhi)
  341.             second = self._dump('-', a, alo, ahi)
  342.         else:
  343.             first = self._dump('-', a, alo, ahi)
  344.             second = self._dump('+', b, blo, bhi)
  345.         for g in (first, second):
  346.             for line in g:
  347.                 yield line
  348.             
  349.         
  350.  
  351.     
  352.     def _fancy_replace(self, a, alo, ahi, b, blo, bhi):
  353.         (best_ratio, cutoff) = (0.74, 0.75)
  354.         cruncher = SequenceMatcher(self.charjunk)
  355.         (eqi, eqj) = (None, None)
  356.         for j in xrange(blo, bhi):
  357.             bj = b[j]
  358.             cruncher.set_seq2(bj)
  359.             for i in xrange(alo, ahi):
  360.                 ai = a[i]
  361.                 if ai == bj:
  362.                     if eqi is None:
  363.                         eqi = i
  364.                         eqj = j
  365.                         continue
  366.                     continue
  367.                 
  368.                 cruncher.set_seq1(ai)
  369.                 if cruncher.real_quick_ratio() > best_ratio and cruncher.quick_ratio() > best_ratio and cruncher.ratio() > best_ratio:
  370.                     best_ratio = cruncher.ratio()
  371.                     best_i = i
  372.                     best_j = j
  373.                     continue
  374.             
  375.         
  376.         if best_ratio < cutoff:
  377.             if eqi is None:
  378.                 for line in self._plain_replace(a, alo, ahi, b, blo, bhi):
  379.                     yield line
  380.                 
  381.                 return None
  382.             
  383.             best_i = eqi
  384.             best_j = eqj
  385.             best_ratio = 1
  386.         else:
  387.             eqi = None
  388.         for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):
  389.             yield line
  390.         
  391.         aelt = a[best_i]
  392.         belt = b[best_j]
  393.         if eqi is None:
  394.             atags = btags = ''
  395.             cruncher.set_seqs(aelt, belt)
  396.             for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():
  397.                 la = ai2 - ai1
  398.                 lb = bj2 - bj1
  399.                 if tag == 'replace':
  400.                     atags += '^' * la
  401.                     btags += '^' * lb
  402.                     continue
  403.                 if tag == 'delete':
  404.                     atags += '-' * la
  405.                     continue
  406.                 if tag == 'insert':
  407.                     btags += '+' * lb
  408.                     continue
  409.                 if tag == 'equal':
  410.                     atags += ' ' * la
  411.                     btags += ' ' * lb
  412.                     continue
  413.                 raise ValueError, 'unknown tag %r' % (tag,)
  414.             
  415.             for line in self._qformat(aelt, belt, atags, btags):
  416.                 yield line
  417.             
  418.         else:
  419.             yield '  ' + aelt
  420.         for line in self._fancy_helper(a, best_i + 1, ahi, b, best_j + 1, bhi):
  421.             yield line
  422.         
  423.  
  424.     
  425.     def _fancy_helper(self, a, alo, ahi, b, blo, bhi):
  426.         g = []
  427.         if alo < ahi:
  428.             if blo < bhi:
  429.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  430.             else:
  431.                 g = self._dump('-', a, alo, ahi)
  432.         elif blo < bhi:
  433.             g = self._dump('+', b, blo, bhi)
  434.         
  435.         for line in g:
  436.             yield line
  437.         
  438.  
  439.     
  440.     def _qformat(self, aline, bline, atags, btags):
  441.         common = min(_count_leading(aline, '\t'), _count_leading(bline, '\t'))
  442.         common = min(common, _count_leading(atags[:common], ' '))
  443.         atags = atags[common:].rstrip()
  444.         btags = btags[common:].rstrip()
  445.         yield '- ' + aline
  446.         if atags:
  447.             yield '? %s%s\n' % ('\t' * common, atags)
  448.         
  449.         yield '+ ' + bline
  450.         if btags:
  451.             yield '? %s%s\n' % ('\t' * common, btags)
  452.         
  453.  
  454.  
  455. import re
  456.  
  457. def IS_LINE_JUNK(line, pat = re.compile('\\s*#?\\s*$').match):
  458.     return pat(line) is not None
  459.  
  460.  
  461. def IS_CHARACTER_JUNK(ch, ws = ' \t'):
  462.     return ch in ws
  463.  
  464.  
  465. def unified_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  466.     started = False
  467.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  468.         if not started:
  469.             yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
  470.             yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
  471.             started = True
  472.         
  473.         (i1, i2, j1, j2) = (group[0][1], group[-1][2], group[0][3], group[-1][4])
  474.         yield '@@ -%d,%d +%d,%d @@%s' % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
  475.         for tag, i1, i2, j1, j2 in group:
  476.             if tag == 'equal':
  477.                 for line in a[i1:i2]:
  478.                     yield ' ' + line
  479.                 
  480.                 continue
  481.             
  482.             if tag == 'replace' or tag == 'delete':
  483.                 for line in a[i1:i2]:
  484.                     yield '-' + line
  485.                 
  486.             
  487.             if tag == 'replace' or tag == 'insert':
  488.                 for line in b[j1:j2]:
  489.                     yield '+' + line
  490.                 
  491.         
  492.     
  493.  
  494.  
  495. def context_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  496.     started = False
  497.     prefixmap = {
  498.         'insert': '+ ',
  499.         'delete': '- ',
  500.         'replace': '! ',
  501.         'equal': '  ' }
  502.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  503.         if not started:
  504.             yield '*** %s %s%s' % (fromfile, fromfiledate, lineterm)
  505.             yield '--- %s %s%s' % (tofile, tofiledate, lineterm)
  506.             started = True
  507.         
  508.         yield '***************%s' % (lineterm,)
  509.         if group[-1][2] - group[0][1] >= 2:
  510.             yield '*** %d,%d ****%s' % (group[0][1] + 1, group[-1][2], lineterm)
  511.         else:
  512.             yield '*** %d ****%s' % (group[-1][2], lineterm)
  513.         visiblechanges = _[1]
  514.         if visiblechanges:
  515.             for tag, i1, i2, _, _ in group:
  516.                 if tag != 'insert':
  517.                     for line in a[i1:i2]:
  518.                         yield prefixmap[tag] + line
  519.                         []
  520.                     
  521.                 []
  522.             
  523.         
  524.         if group[-1][4] - group[0][3] >= 2:
  525.             yield '--- %d,%d ----%s' % (group[0][3] + 1, group[-1][4], lineterm)
  526.         else:
  527.             yield '--- %d ----%s' % (group[-1][4], lineterm)
  528.         visiblechanges = _[2]
  529.         if visiblechanges:
  530.             for tag, _, _, j1, j2 in group:
  531.                 if tag != 'delete':
  532.                     for line in b[j1:j2]:
  533.                         yield prefixmap[tag] + line
  534.                         []
  535.                     
  536.                 []
  537.             
  538.     
  539.  
  540.  
  541. def ndiff(a, b, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  542.     return Differ(linejunk, charjunk).compare(a, b)
  543.  
  544.  
  545. def _mdiff(fromlines, tolines, context = None, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  546.     import re
  547.     change_re = re.compile('(\\++|\\-+|\\^+)')
  548.     diff_lines_iterator = ndiff(fromlines, tolines, linejunk, charjunk)
  549.     
  550.     def _make_line(lines, format_key, side, num_lines = ([
  551.         0,
  552.         0],)):
  553.         num_lines[side] += 1
  554.         if format_key is None:
  555.             return (num_lines[side], lines.pop(0)[2:])
  556.         
  557.         if format_key == '?':
  558.             text = lines.pop(0)
  559.             markers = lines.pop(0)
  560.             sub_info = []
  561.             
  562.             def record_sub_info(match_object, sub_info = sub_info):
  563.                 sub_info.append([
  564.                     match_object.group(1)[0],
  565.                     match_object.span()])
  566.                 return match_object.group(1)
  567.  
  568.             change_re.sub(record_sub_info, markers)
  569.             for begin, end in sub_info[::-1]:
  570.                 text = text[0:begin] + '\x00' + key + text[begin:end] + '\x01' + text[end:]
  571.             
  572.             text = text[2:]
  573.         else:
  574.             text = lines.pop(0)[2:]
  575.             if not text:
  576.                 text = ' '
  577.             
  578.             text = '\x00' + format_key + text + '\x01'
  579.         return (num_lines[side], text)
  580.  
  581.     
  582.     def _line_iterator():
  583.         lines = []
  584.         (num_blanks_pending, num_blanks_to_yield) = (0, 0)
  585.         for line in lines:
  586.             s = _[1](_[1][line[0]])
  587.             if s.startswith('X'):
  588.                 num_blanks_to_yield = num_blanks_pending
  589.             elif s.startswith('-?+?'):
  590.                 yield (_make_line(lines, '?', 0), _make_line(lines, '?', 1), True)
  591.                 []
  592.                 continue
  593.             elif s.startswith('--++'):
  594.                 num_blanks_pending -= 1
  595.                 yield (_make_line(lines, '-', 0), None, True)
  596.                 continue
  597.             elif s.startswith(('--?+', '--+', '- ')):
  598.                 from_line = _make_line(lines, '-', 0)
  599.                 to_line = None
  600.                 num_blanks_to_yield = num_blanks_pending - 1
  601.                 num_blanks_pending = 0
  602.             elif s.startswith('-+?'):
  603.                 yield (_make_line(lines, None, 0), _make_line(lines, '?', 1), True)
  604.                 continue
  605.             elif s.startswith('-?+'):
  606.                 yield (_make_line(lines, '?', 0), _make_line(lines, None, 1), True)
  607.                 continue
  608.             elif s.startswith('-'):
  609.                 num_blanks_pending -= 1
  610.                 yield (_make_line(lines, '-', 0), None, True)
  611.                 continue
  612.             elif s.startswith('+--'):
  613.                 num_blanks_pending += 1
  614.                 yield (None, _make_line(lines, '+', 1), True)
  615.                 continue
  616.             elif s.startswith(('+ ', '+-')):
  617.                 from_line = None
  618.                 to_line = _make_line(lines, '+', 1)
  619.                 num_blanks_to_yield = num_blanks_pending + 1
  620.                 num_blanks_pending = 0
  621.             elif s.startswith('+'):
  622.                 num_blanks_pending += 1
  623.                 yield (None, _make_line(lines, '+', 1), True)
  624.                 continue
  625.             elif s.startswith(' '):
  626.                 yield (_make_line(lines[:], None, 0), _make_line(lines, None, 1), False)
  627.                 continue
  628.             
  629.             while num_blanks_to_yield < 0:
  630.                 num_blanks_to_yield += 1
  631.                 yield (None, ('', '\n'), True)
  632.             while num_blanks_to_yield > 0:
  633.                 num_blanks_to_yield -= 1
  634.                 yield (('', '\n'), None, True)
  635.             if s.startswith('X'):
  636.                 raise StopIteration
  637.                 continue
  638.             yield (from_line, to_line, True)
  639.  
  640.     
  641.     def _line_pair_iterator():
  642.         line_iterator = _line_iterator()
  643.         fromlines = []
  644.         tolines = []
  645.         while True:
  646.             while len(fromlines) == 0 or len(tolines) == 0:
  647.                 (from_line, to_line, found_diff) = line_iterator.next()
  648.                 if from_line is not None:
  649.                     fromlines.append((from_line, found_diff))
  650.                 
  651.                 if to_line is not None:
  652.                     tolines.append((to_line, found_diff))
  653.                     continue
  654.             (from_line, fromDiff) = fromlines.pop(0)
  655.             (to_line, to_diff) = tolines.pop(0)
  656.             if not fromDiff:
  657.                 pass
  658.             yield (from_line, to_line, to_diff)
  659.  
  660.     line_pair_iterator = _line_pair_iterator()
  661.     if context is None:
  662.         while True:
  663.             yield line_pair_iterator.next()
  664.             ((None, None),)
  665.     else:
  666.         context += 1
  667.         lines_to_write = 0
  668.         while True:
  669.             index = 0
  670.             contextLines = [
  671.                 None] * context
  672.             found_diff = False
  673.             while found_diff is False:
  674.                 (from_line, to_line, found_diff) = line_pair_iterator.next()
  675.                 i = index % context
  676.                 contextLines[i] = (from_line, to_line, found_diff)
  677.                 index += 1
  678.                 continue
  679.                 ((None, None),)
  680.             if index > context:
  681.                 yield (None, None, None)
  682.                 lines_to_write = context
  683.             else:
  684.                 lines_to_write = index
  685.                 index = 0
  686.             while lines_to_write:
  687.                 i = index % context
  688.                 index += 1
  689.                 yield contextLines[i]
  690.                 lines_to_write -= 1
  691.             lines_to_write = context - 1
  692.             while lines_to_write:
  693.                 (from_line, to_line, found_diff) = line_pair_iterator.next()
  694.                 if found_diff:
  695.                     lines_to_write = context - 1
  696.                 else:
  697.                     lines_to_write -= 1
  698.                 yield (from_line, to_line, found_diff)
  699.  
  700. _file_template = '\n<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"\n          "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">\n\n<html>\n\n<head>\n    <meta http-equiv="Content-Type"\n          content="text/html; charset=ISO-8859-1" />\n    <title></title>\n    <style type="text/css">%(styles)s\n    </style>\n</head>\n\n<body>\n    %(table)s%(legend)s\n</body>\n\n</html>'
  701. _styles = '\n        table.diff {font-family:Courier; border:medium;}\n        .diff_header {background-color:#e0e0e0}\n        td.diff_header {text-align:right}\n        .diff_next {background-color:#c0c0c0}\n        .diff_add {background-color:#aaffaa}\n        .diff_chg {background-color:#ffff77}\n        .diff_sub {background-color:#ffaaaa}'
  702. _table_template = '\n    <table class="diff" id="difflib_chg_%(prefix)s_top"\n           cellspacing="0" cellpadding="0" rules="groups" >\n        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n        %(header_row)s\n        <tbody>\n%(data_rows)s        </tbody>\n    </table>'
  703. _legend = '\n    <table class="diff" summary="Legends">\n        <tr> <th colspan="2"> Legends </th> </tr>\n        <tr> <td> <table border="" summary="Colors">\n                      <tr><th> Colors </th> </tr>\n                      <tr><td class="diff_add"> Added </td></tr>\n                      <tr><td class="diff_chg">Changed</td> </tr>\n                      <tr><td class="diff_sub">Deleted</td> </tr>\n                  </table></td>\n             <td> <table border="" summary="Links">\n                      <tr><th colspan="2"> Links </th> </tr>\n                      <tr><td>(f)irst change</td> </tr>\n                      <tr><td>(n)ext change</td> </tr>\n                      <tr><td>(t)op</td> </tr>\n                  </table></td> </tr>\n    </table>'
  704.  
  705. class HtmlDiff(object):
  706.     _file_template = _file_template
  707.     _styles = _styles
  708.     _table_template = _table_template
  709.     _legend = _legend
  710.     _default_prefix = 0
  711.     
  712.     def __init__(self, tabsize = 8, wrapcolumn = None, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  713.         self._tabsize = tabsize
  714.         self._wrapcolumn = wrapcolumn
  715.         self._linejunk = linejunk
  716.         self._charjunk = charjunk
  717.  
  718.     
  719.     def make_file(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5):
  720.         return self._file_template % dict(styles = self._styles, legend = self._legend, table = self.make_table(fromlines, tolines, fromdesc, todesc, context = context, numlines = numlines))
  721.  
  722.     
  723.     def _tab_newline_replace(self, fromlines, tolines):
  724.         
  725.         def expand_tabs(line):
  726.             line = line.replace(' ', '\x00')
  727.             line = line.expandtabs(self._tabsize)
  728.             line = line.replace(' ', '\t')
  729.             return line.replace('\x00', ' ').rstrip('\n')
  730.  
  731.         fromlines = [ expand_tabs(line) for line in fromlines ]
  732.         tolines = [ expand_tabs(line) for line in tolines ]
  733.         return (fromlines, tolines)
  734.  
  735.     
  736.     def _split_line(self, data_list, line_num, text):
  737.         if not line_num:
  738.             data_list.append((line_num, text))
  739.             return None
  740.         
  741.         size = len(text)
  742.         max = self._wrapcolumn
  743.         if size <= max or size - text.count('\x00') * 3 <= max:
  744.             data_list.append((line_num, text))
  745.             return None
  746.         
  747.         i = 0
  748.         n = 0
  749.         mark = ''
  750.         while n < max and i < size:
  751.             if text[i] == '\x00':
  752.                 i += 1
  753.                 mark = text[i]
  754.                 i += 1
  755.                 continue
  756.             if text[i] == '\x01':
  757.                 i += 1
  758.                 mark = ''
  759.                 continue
  760.             i += 1
  761.             n += 1
  762.         line1 = text[:i]
  763.         line2 = text[i:]
  764.         if mark:
  765.             line1 = line1 + '\x01'
  766.             line2 = '\x00' + mark + line2
  767.         
  768.         data_list.append((line_num, line1))
  769.         self._split_line(data_list, '>', line2)
  770.  
  771.     
  772.     def _line_wrapper(self, diffs):
  773.         for fromdata, todata, flag in diffs:
  774.             if flag is None:
  775.                 yield (fromdata, todata, flag)
  776.                 continue
  777.             
  778.             (fromline, fromtext) = fromdata
  779.             (toline, totext) = todata
  780.             fromlist = []
  781.             tolist = []
  782.             self._split_line(fromlist, fromline, fromtext)
  783.             self._split_line(tolist, toline, totext)
  784.             while fromlist or tolist:
  785.                 if fromlist:
  786.                     fromdata = fromlist.pop(0)
  787.                 else:
  788.                     fromdata = ('', ' ')
  789.                 if tolist:
  790.                     todata = tolist.pop(0)
  791.                 else:
  792.                     todata = ('', ' ')
  793.                 yield (fromdata, todata, flag)
  794.         
  795.  
  796.     
  797.     def _collect_lines(self, diffs):
  798.         fromlist = []
  799.         tolist = []
  800.         flaglist = []
  801.         for fromdata, todata, flag in diffs:
  802.             
  803.             try:
  804.                 fromlist.append(self._format_line(0, flag, *fromdata))
  805.                 tolist.append(self._format_line(1, flag, *todata))
  806.             except TypeError:
  807.                 fromlist.append(None)
  808.                 tolist.append(None)
  809.  
  810.             flaglist.append(flag)
  811.         
  812.         return (fromlist, tolist, flaglist)
  813.  
  814.     
  815.     def _format_line(self, side, flag, linenum, text):
  816.         
  817.         try:
  818.             linenum = '%d' % linenum
  819.             id = ' id="%s%s"' % (self._prefix[side], linenum)
  820.         except TypeError:
  821.             id = ''
  822.  
  823.         text = text.replace('&', '&').replace('>', '>').replace('<', '<')
  824.         text = text.replace(' ', ' ').rstrip()
  825.         return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' % (id, linenum, text)
  826.  
  827.     
  828.     def _make_prefix(self):
  829.         fromprefix = 'from%d_' % HtmlDiff._default_prefix
  830.         toprefix = 'to%d_' % HtmlDiff._default_prefix
  831.         HtmlDiff._default_prefix += 1
  832.         self._prefix = [
  833.             fromprefix,
  834.             toprefix]
  835.  
  836.     
  837.     def _convert_flags(self, fromlist, tolist, flaglist, context, numlines):
  838.         toprefix = self._prefix[1]
  839.         next_id = [
  840.             ''] * len(flaglist)
  841.         next_href = [
  842.             ''] * len(flaglist)
  843.         num_chg = 0
  844.         in_change = False
  845.         last = 0
  846.         for i, flag in enumerate(flaglist):
  847.             if flag:
  848.                 if not in_change:
  849.                     in_change = True
  850.                     last = i
  851.                     i = max([
  852.                         0,
  853.                         i - numlines])
  854.                     next_id[i] = ' id="difflib_chg_%s_%d"' % (toprefix, num_chg)
  855.                     num_chg += 1
  856.                     next_href[last] = '<a href="#difflib_chg_%s_%d">n</a>' % (toprefix, num_chg)
  857.                 
  858.             in_change
  859.             in_change = False
  860.         
  861.         if not flaglist:
  862.             flaglist = [
  863.                 False]
  864.             next_id = [
  865.                 '']
  866.             next_href = [
  867.                 '']
  868.             last = 0
  869.             if context:
  870.                 fromlist = [
  871.                     '<td></td><td> No Differences Found </td>']
  872.                 tolist = fromlist
  873.             else:
  874.                 fromlist = tolist = [
  875.                     '<td></td><td> Empty File </td>']
  876.         
  877.         if not flaglist[0]:
  878.             next_href[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
  879.         
  880.         next_href[last] = '<a href="#difflib_chg_%s_top">t</a>' % toprefix
  881.         return (fromlist, tolist, flaglist, next_href, next_id)
  882.  
  883.     
  884.     def make_table(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5):
  885.         self._make_prefix()
  886.         (fromlines, tolines) = self._tab_newline_replace(fromlines, tolines)
  887.         if context:
  888.             context_lines = numlines
  889.         else:
  890.             context_lines = None
  891.         diffs = _mdiff(fromlines, tolines, context_lines, linejunk = self._linejunk, charjunk = self._charjunk)
  892.         if self._wrapcolumn:
  893.             diffs = self._line_wrapper(diffs)
  894.         
  895.         (fromlist, tolist, flaglist) = self._collect_lines(diffs)
  896.         (fromlist, tolist, flaglist, next_href, next_id) = self._convert_flags(fromlist, tolist, flaglist, context, numlines)
  897.         s = []
  898.         fmt = '            <tr><td class="diff_next"%s>%s</td>%s' + '<td class="diff_next">%s</td>%s</tr>\n'
  899.         for i in range(len(flaglist)):
  900.             if flaglist[i] is None:
  901.                 if i > 0:
  902.                     s.append('        </tbody>        \n        <tbody>\n')
  903.                 
  904.             i > 0
  905.             s.append(fmt % (next_id[i], next_href[i], fromlist[i], next_href[i], tolist[i]))
  906.         
  907.         if fromdesc or todesc:
  908.             header_row = '<thead><tr>%s%s%s%s</tr></thead>' % ('<th class="diff_next"><br /></th>', '<th colspan="2" class="diff_header">%s</th>' % fromdesc, '<th class="diff_next"><br /></th>', '<th colspan="2" class="diff_header">%s</th>' % todesc)
  909.         else:
  910.             header_row = ''
  911.         table = self._table_template % dict(data_rows = ''.join(s), header_row = header_row, prefix = self._prefix[1])
  912.         return table.replace('\x00+', '<span class="diff_add">').replace('\x00-', '<span class="diff_sub">').replace('\x00^', '<span class="diff_chg">').replace('\x01', '</span>').replace('\t', ' ')
  913.  
  914.  
  915. del re
  916.  
  917. def restore(delta, which):
  918.     
  919.     try:
  920.         tag = {
  921.             1: '- ',
  922.             2: '+ ' }[int(which)]
  923.     except KeyError:
  924.         raise ValueError, 'unknown delta choice (must be 1 or 2): %r' % which
  925.  
  926.     prefixes = ('  ', tag)
  927.     for line in delta:
  928.         if line[:2] in prefixes:
  929.             yield line[2:]
  930.             continue
  931.     
  932.  
  933.  
  934. def _test():
  935.     import doctest
  936.     import difflib
  937.     return doctest.testmod(difflib)
  938.  
  939. if __name__ == '__main__':
  940.     _test()
  941.  
  942.